package org.nowcoder.leetcode.DP;

import java.util.List;

/**
 * Title  : 120. Triangle
 * Source : https://leetcode.cn/problems/triangle/description/
 * Author : XrazYang
 * Date   : 2023-12-21
 */

public class LeetCode_120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size();

        //1. 定义状态: dp[i][j], [0][0] ---> [i][j] 最短路径
        int[][] dp = new int[len][len];

        //2. 初始状态
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < len; i++) {
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
        }

        //3. 状态转换方程
        int min = dp[len - 1][0];
        for (int i = 1; i < len; i++) {
            List<Integer> pre = triangle.get(i - 1);
            List<Integer> line = triangle.get(i);
            for (int j = 1; j < line.size(); j++) {
                Integer k = line.get(j);
                if (j == pre.size()) {
                    dp[i][j] = dp[i - 1][j - 1] + k;
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + k;
                }
                if (i == len - 1) {
                    min = Math.min(dp[i][j], min);
                }
            }
        }
        return min;
    }
}
